#include "../tools.h"
#include "../ztools/tools_hash.h"

struct TrieNode{
    int val;
    TrieNode* next[26];
    TrieNode(){
        val = 0;
        for(int i = 0; i < 26; ++i)
            next[i] = nullptr;
    }
};

class MapSum {
public:
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        int delta = val;
        if(dict.count(key)){
            delta -= dict[key];
        }
        dict[key] = val;

        TrieNode* node = root;
        for(auto c: key){
            if(node->next[c - 'a'] == nullptr)
                node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
            node->val += delta;
        }
    }
    
    int sum(string prefix) {
        TrieNode* node = root;
        for(auto c: prefix){
            if(node->next[c - 'a'] == 0) return 0;
            else node = node->next[c - 'a'];
        }
        return node->val;
    }
private:
    unordered_map<string, int> dict;
    TrieNode* root;
};


int main(int argc, char const *argv[])
{
    MapSum ms;

    ms.insert("apple", 3);
    cout << ms.sum("ap") << endl;
    ms.insert("app", 2);
    ms.insert("apple", 2);
    cout << ms.sum("ap") << endl;





    return 0;
}
